def counting_sort_by_digit(arr, digit_place):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 只有 0~9 这10个数字

    # 计算每个数字出现的次数
    for num in arr:
        digit = (num // digit_place) % 10
        count[digit] += 1

    # 将 count 数组变成“位置索引”
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 稳定排序，从后往前放
    for i in reversed(range(n)):
        digit = (arr[i] // digit_place) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1

    return output


def radix_sort(arr):
    # 找最大数，决定排序多少轮
    max_num = max(arr)
    digit_place = 1

    while max_num // digit_place > 0:
        arr = counting_sort_by_digit(arr, digit_place)
        digit_place *= 10

    return arr
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print(sorted_arr)
# 输出: [2, 24, 45, 66, 75, 90, 170, 802]
s='sgreg'

